<?php
/*
 * 有序数组 arr 可能经过一次旋转处理，也可能没有， * 且 arr 可能存在重复的数。
 * 例如，
 * 有序 数组[1,2,3,4,5,6,7]，可以旋转处理成[4,5,6,7,1,2,3]等。
 * 给定一个可能旋转过的有序数组 arr，返回 arr 中的最小值。
 */

$arr = [4, 5, 6, 7, 1, 2, 3];
$obj = new Middle_Day08_Code_01();
$res = $obj->main($arr);
echo $res;


class Middle_Day08_Code_01
{
    public function main($arr)
    {
        $low  = 0;
        $high = count($arr) - 1;
        // 潜台词：L..R有全局min
        while ($low < $high) {
            if ($low == $high - 1) {
                break;
            }
            // arr[L] < arr[R] L~R的范围上没有旋转
            if ($arr[$low] < $arr[$high]) {
                return $arr[$low];
            }
            // [L] >= [R]
            $mid = intval(($low + $high) / 2);
            if ($arr[$low] > $arr[$mid]) {
                $high = $mid;
                continue;
            }
            // [L] >= [R] && [mid] >= [L]
            if ($arr[$mid] > $arr[$high]) {
                $low = $mid;
                continue;
            }
            // [L] >= [R] && [mid] >= [L] && [mid] <= [R]
            // ==> [L] == [mid] == [R]
            while ($low < $mid) {
                if ($arr[$low] == $arr[$mid]) {
                    $low++;
                } else if ($arr[$low] < $arr[$mid]) {
                    return $arr[$low];
                } else {
                    $high = $mid;
                    break;
                }
            }
        }
        return min($arr[$low], $arr[$high]);
    }


}